package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 买卖股票的最佳时机含手续费
    static class Solution {
        public int maxProfit(int[] prices, int fee) {
            // 1) 边界处理
            if (prices == null || prices.length < 2) return 0;

            int n = prices.length;
            // 2) 定义 dp[i][j]：第 i 天结束时的最大利润
            //    j=0 表示持有股票，j=1 表示不持有股票
            int[][] dp = new int[n + 1][2];

            // 3) 初始化：第 0 天持有股票是不可能的状态
            dp[0][0] = Integer.MIN_VALUE / 2; // 防止溢出
            dp[0][1] = 0; // 第 0 天不持有股票，利润为 0

            // 4) 状态转移：遍历每一天
            for (int i = 1; i <= n; i++) {
                // 今天持有 = max(昨天就持有, 昨天不持有今天买入)
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i - 1]);
                // 今天不持有 = max(昨天就不持有, 昨天持有今天卖出-手续费)
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i - 1] - fee);
            }

            // 5) 返回最后一天不持有股票的最大利润
            return dp[n][1];
        }
    }
}